/*  P55  
**  ElementType = int;
**  
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXSIZE 16384
#define ERROR -1

struct LNode {
    int Data[MAXSIZE];
    int Last;
};

typedef int Position;

typedef struct LNode* PtrToLNode;

typedef PtrToLNode List;

List MakeEmpty();

Position FindKth ( List L, int i ); 

Position Find ( List L, int X );

bool Insert ( List L, int X, int i ); 

bool Delete ( List L, int i );

Position Length ( List L );

int main ( int argc, char const *argv[] ) {
    PtrToLNode L;
    Position X, i, result, num, len;
    L = MakeEmpty();

    /* insert */
    printf("Input\nPlease input how much data you want to insert\n");
    scanf("%d",&num);
    for( i = 1; i <= num; i++ ) {
        printf("Insert from begin to end\nPlease insert the %dst data\n",i);
        scanf("%d",&X);
        Insert(L, X, i);
    }

    len = Length(L);
    printf("Length is %d\n",len);

    printf("data\n");
    for ( i = 0; i <= L->Last; i++ ) {
        X = FindKth(L, i);
        printf("%d\t|\t%d\n",i,X);
    }

    /* find */
    printf("Find\nPlease input value of X\n");
    scanf("%d",&X);
    result = Find(L, X);
    if ( result == ERROR ) {
        printf("Can't find the data\n");
    } else {
        printf("%d is in the %dth place\n", X, result);
    }
    
    /* delete */
    printf("Delete\nPlease input the location of the data you want to delete\n");
    scanf("%d",&i);
    Delete(L, i);

    printf("data\n");
    for ( i = 0; i <= L->Last; i++ ) {
        X = FindKth(L, i);
        printf("%d\t|\t%d\n",i+1,X);
    }
    len = Length(L);
    printf("Length is %d\n",len);
    
    free(L);
    
    return  0;
}

Position FindKth ( List L, int i ) {
    return L->Data[i];
}

List MakeEmpty() {
    List L;
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
    return L;
}

Position Find ( List L, int X ) {
    Position i = 0;
    while ( i <= L->Last && L->Data[i] != X ) i++;
    if ( i > L->Last ) return ERROR;
    else return i;
}

bool Insert ( List L, int X, int i ) {
    Position j;

    if ( L->Last == MAXSIZE - 1 ) {
        printf("FULL\n");
        return false;
    } 
    
    if ( i < 1 || i > L->Last+2 ) {
        printf("Wrong Position\n");
        return false;
    } 

    for ( j = L->Last; j >= i-1; j-- ) L->Data[j+1] = L->Data[j];
    L->Data[i-1] = X;
    L->Last++;
    printf("Success Insert\n");
    return true;
}

bool Delete ( List L, int i ) {
    Position j;
    
    if ( i < 1 || i > L->Last + 1 ) {
        printf("No element in the %dth position\n",i);
        return false;
    }

    for ( j = i; j <= L->Last; j++ ) L->Data[j-1] = L->Data[j];
    L->Last--;
    printf("Suceess Delete\n");
    return true;
}

Position Length ( List L ) {
    return L->Last+1;
}